%!TEX root = paper.tex

The most effective way to explore data is through visualizing the
results of exploration queries. For example, an exploration query
could be an aggregate of some measures over time intervals, and a
pattern or abnormality can be discovered through a time series plot of
the query results.  In this paper, we examine a special kind of
exploration query, namely object-centric exploration query. Common
examples include claims made about athletes in sports databases, such
as ``it is newsworthy that LeBron James has scored 35 or more points
in nine consecutive games.''

%  In fact, object-centric exploration queries are powerful mechanisms
% to analyze users of search engines in order to identify patterns and
% abnormalities.

%All types of claims are made about facts based on data.  One common
%type of analysis to examine the quality of a claim is to compare it
%with other claims of the same form.  Such exploratory analysis can
%usually be carried out effectively via visualization.

We focus on one common type of visualization, i.e., 2d scatter plot
with heatmap. Namely, we consider exploration queries whose results
can be plotted on a two-dimensional space, possibly with colors
indicating object densities in regions.  While we model results as
pairs of numbers, the types of the queries are limited only by the
users' imagination.  In the LeBron James example above, the two
dimensions are minimum points scored per game and number of
consecutive games, respectively.  It is easy to find other equally
interesting dimensions, such as minimum rebounds per game or number of
playoff games.

We formalize this problem and propose an efficient, interactive-speed
algorithm that takes a user-provided exploration query (which can be a
blackbox function) and produces an approximate visualization that
preserves the two most important visual properties: the outliers and
the overall distribution of all result points.

%Results of different types of claims may have the same
%format of representation, e.g. 2D points.  We treat a claim type as
%a function that maps a set of input tuples to a multiset of 2d points.
